// 链表 的 技巧 与 常用方法
// 1.画图 - 链表的题目大多数都是模拟题，画图能够使模拟过程更加清晰
// 2.引入虚拟头结点 newHead，目的是为了让尾指针具备一般性，一个循环搞定代码
// 3.不吝啬空间，敢于定义变量 prev, next等：prev - 前边链的尾指针  next - 后边链的头指针 有头有尾，不怕链断
// 4.快慢双指针 - 判断环，找环的入口，找链表中的倒数第 n 个节点
// 5.创建新节点
// 6.尾插法 - 定义尾节点 tail，维护尾节点
// 7.头插法 - 引入虚拟头结点 newHead: node -> newHead.next, newHead.next -> node
// 8.合并多个有序数组或者合并多个链表，见到“合并”两个字，必须要想起来分治的思想

// 例题 4：
// 给你一个链表数组，每个链表都已经按升序排列。
//
//        请你将所有链表合并到一个升序链表中，返回合并后的链表。
//
//        示例 1：
//
//        输入：lists = [[1,4,5],[1,3,4],[2,6]]
//        输出：[1,1,2,3,4,4,5,6]
//        解释：链表数组如下：
//        [
//        1->4->5,
//        1->3->4,
//        2->6
//        ]
//        将它们合并到一个有序链表中得到。
//        1->1->2->3->4->4->5->6
//        示例 2：
//
//        输入：lists = []
//        输出：[]
//        示例 3：
//
//        输入：lists = [[]]
//        输出：[]
//
//
//        提示：
//
//        k == lists.length
//        0 <= k <= 10^4
//        0 <= lists[i].length <= 500
//        -10^4 <= lists[i][j] <= 10^4
//        lists[i] 按 升序 排列
//        lists[i].length 的总和不超过 10^4

// 解题思路：

// 解法一：
// 使用优先级队列（小根堆）将所有链表头结点加入队列
// 每次弹出一个最小的，尾插到新链表的后面
// 弹出的头结点，如果有下一个节点就继续加入队列
// 直到队列为空，就表示已经排序好了所有节点

// 解法二：
// 采用分治的思想，先合并左半部分，再合并右半部分，最后再合并两个有序链表

import java.util.PriorityQueue;

public class MergeKLists {
    // 解法 1：优先级队列
    public ListNode mergeKLists1(ListNode[] lists) {
        int k = lists.length;
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        for(int i = 0; i < k; i++){
            if(lists[i] != null) {
                heap.offer(lists[i]);
                lists[i] = lists[i].next;
            }
        }
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while(!heap.isEmpty()){
            ListNode tmp = heap.poll();
            cur.next = tmp;
            cur = cur.next;
            if(tmp.next != null) heap.offer(tmp.next);
        }
        return head.next;
    }

    // 解法 2：分治递归
    public ListNode mergeKLists2(ListNode[] lists) {
        int k = lists.length;
        return merge(lists, 0, k - 1);
    }
    public ListNode merge(ListNode[] lists, int left, int right){
        if(left > right) return null;
        else if(left == right) return lists[left];
        int mid = left + (right - left) / 2;
        ListNode leftHead = merge(lists, left, mid);
        ListNode rightHead = merge(lists, mid + 1, right);

        ListNode cur1 = leftHead;
        ListNode cur2 = rightHead;
        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        while(cur1 != null && cur2 != null){
            if(cur1.val <= cur2.val){
                cur.next = cur1;
                cur = cur1;
                cur1 = cur1.next;
            }else{
                cur.next = cur2;
                cur = cur2;
                cur2 = cur2.next;
            }
        }
        if(cur1 != null) cur.next = cur1;
        if(cur2 != null) cur.next = cur2;
        return newHead.next;
    }
}
